package ACwing.P2DataSturcture.Trie;

import java.io.*;

/**
 * @Date : 2023-03-08
 * @Description:835. Trie字符串统计
 * 构造Trie树，是利用数组（每个节点是字符值+下一字符的索引）
 *
 */
public class TrieString {
    static int N=100010;
    static int [][] son=new int[N][26];//最多26个字母
    static int [] cnt=new int[N];//以当前节点结束的单词有多少个
    static int idx;//当前用到的下标，下标是0的点既是根节点又是空节点
    static char[]str=new char[N];//插入查询的单词
    public static void main(String[] args) throws IOException {
    BufferedReader br=  new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw=  new BufferedWriter(new OutputStreamWriter(System.out));
    int n;
    n=Integer.valueOf(br.readLine());
    while(n--!=0){
        char[] op=new char[2];
        String[] split = br.readLine().split("\\s+");
        op = split[0].toCharArray();
        str = split[1].toCharArray();
        if(op[0]=='I') insert(str);
        else {bw.write(query(str));bw.newLine();}
    }
        bw.flush();

    }
    //插入单词
    static void insert(char str[]){
        int p=0;
        for (int i = 0; i<str.length; i++) {
            int u=str[i]-'a';//找对应子节点编号
            if(son[p][u]==0) son[p][u]=++idx;
            p=son[p][u];
        }
        cnt[p]++;
    }
    //查询单词出现次数
    static String query(char str[]){
        int p=0;
        for (int i = 0; i<str.length; i++) {
            int u=str[i]-'a';//找对应子节点编号
            if(son[p][u]==0) return "0";
            p=son[p][u];
        }
        return String.valueOf(cnt[p]);
    }
}
